/*
 * anh.c
 *
 *  Created on: 17 sept. 2013
 *      Author: the
 */
#include"anh.h"
#define DEBUGANH 0

//indicates if the node id1 is in the 3-neighborhood of node id2
//return 1 if yes and 0 otherwise
int is3Neighbor(int id1, int id2)
{
	int i,k;

	//If id1=id2 or they are neighbor, then they are NOT 3-hop neighbor (return 0)
	if ((id1==id2)||(isNeighbor(id1,id2)) || (is2Neighbor(id1,id2)))
		return 0;


	for (i=0;i<nodes[id2].nbN2;i++)
	{
		k=nodes[id2].N2[i].id;

		//If we find a common neighbor, they are 2-hop neighbor, return 1
		if (isNeighbor(id1,k)){
//			if(DEBUGANH) fprintf(stderr,"%d et %d sont 3 voisins : au travers du 2vois=%d\n",id1,id2,k);
			return 1;
		}
	}

	return 0;
}

//Return 1, s'il y a la frequence de noeud "emetteur" vers "recepteur" sur une route active
// et il n'exist pas la route de noeud "recepteur" vers "emetteur"
//Si non, returns 0.
int linkIsDirectionnel(int emetteur, int recepteur)
{
	if( (linkIsActive(emetteur,recepteur)) && (!linkIsActive(recepteur,emetteur)) )
		return 1;

	return 0;
}

//Return 1 if the frequency "frequency" is used between the nodes "emetteur" and "recepteur" for an active route
//Otherwise, returns 0.
int linkFrequencyRouteDirectionnel(int emetteur, int recepteur, int frequency)
{
	int condNode1=1, condNode2=1;

	// Verifier que le noeud emetteur et recepteur utilisent la fréquence 'frequency' pour communication
	condNode1= linkUsedFrequency(emetteur, recepteur, frequency);

	//Test if the link direction is active (there is a route using it)
	if( !linkIsDirectionnel(emetteur,recepteur) || linkIsDirectionnel(recepteur,emetteur) )
		condNode2=0;

	return (condNode1*condNode2);
}

//Compute the conflict graph for a link bidirectional with a conflict at 3 hops.
int conflictGraphLink2(int id1, int id2, int frequency)
{
    int i, j, idN1, idN2, idN3, conflict=0;

    // si id1 et id2 ne sont pas de voisin
    if(isNeighbor(id1,id2)==0)
    	return -1;

	// The Anh : ne compte pas le lien sans frequence
	if( VIDE==frequency)
		return -1;



    /////////////////////////////////////
    //  Traitement auprès du noeud id1 //
    /////////////////////////////////////
	for(i=0;i<nodes[id1].nbN1;i++)
	{
		idN1=nodes[id1].N1[i].id;//index of the neighbor

		//direct neighbor
		if( linkFrequencyRoute(id1,idN1,frequency) && (idN1!=id2)){
			conflict++;
			if(DEBUGANH) printf("link (%d,%d) in conflict-1: %d\n",id1,idN1,conflict);
		}

		//2 1-neighbors together
		for(j=i+1;j<nodes[id1].nbN1;j++){
			if(linkFrequencyRoute(idN1,nodes[id1].N1[j].id,frequency)==1){
				conflict++;
				if(DEBUGANH) printf("link (%d,%d) in conflict-2; %d\n",idN1,nodes[id1].N1[j].id,conflict);
			}
		}

		//neighbor with 2-neighbors
		for(j=0;j<nodes[id1].nbN2;j++){
			if(linkFrequencyRoute(idN1,nodes[id1].N2[j].id,frequency)==1){
				conflict++;
				if(DEBUGANH) printf("link (%d,%d) in conflict-3; %d \n",idN1,nodes[id1].N2[j].id,conflict);
			}
		}

	}

	//2 2-neighbors together
	for(i=0;i<nodes[id1].nbN2;i++)
	{
		idN2 = nodes[id1].N2[i].id;//index of the neighbor
		for(j=i+1;j<nodes[id1].nbN2;j++)
		{
			if(linkFrequencyRoute(idN2,nodes[id1].N2[j].id,frequency)==1)
			{
				conflict++;
				if(DEBUGANH) printf("link (%d,%d) in conflict-4; %d\n",idN2,nodes[id1].N2[j].id,conflict);
			}
		}
	}

	//neighbor with 3-neighbors of node id1
	for(i=0;i<nodes[id1].nbN2;i++)
	{
		idN2 = nodes[id1].N2[i].id;
		for(j = 0 ; j < nodes[idN2].nbN1;j++)
		{
			idN3 = nodes[idN2].N1[j].id;

			if( is3Neighbor(idN3,id1) && (linkFrequencyRoute(idN2,idN3,frequency)==1) )
			{
				conflict++;
				if(DEBUGANH) printf("link (%d,%d) in conflict-5 ; %d\n",idN2,idN3,conflict);
			}
		}
	}


	   /////////////////////////////////////
	   //  Traitement auprès du noeud id2 //
	   /////////////////////////////////////

		//2 2-neighbors together
		for(i=0;i<nodes[id2].nbN2;i++)
		{
			idN2 = nodes[id2].N2[i].id;//index of the neighbor
			for(j=i+1;j<nodes[id2].nbN2;j++)
			{
				if(linkFrequencyRoute(idN2,nodes[id2].N2[j].id,frequency)==1)
				{
					conflict++;
					if(DEBUGANH) printf("link (%d,%d) in conflict-6; %d\n",idN2,nodes[id2].N2[j].id,conflict);
				}
			}
		}

      // 3-neighbors of node id2
		for(i = 0 ; i < nodes[id2].nbN2;i++)
		{
			idN2 = nodes[id2].N2[i].id;
			for(j = 0 ; j < nodes[idN2].nbN1;j++)
			{
				idN3 = nodes[idN2].N1[j].id;

				// idN3 est le voisinage 3-sauts de id2
				if( linkFrequencyRoute(idN2,idN3,frequency)==1 && (is3Neighbor(idN3,id2)==1)
				 && (isNeighbor(id1,idN3)==0) && (is2Neighbor(id1,idN3)==0) && (is3Neighbor(id1,idN3)==0))  // et idN3 n'est pas de voisinage 1,2,3 saut de id1
				{
					conflict ++;
					if(DEBUGANH) printf("link (%d,%d) in conflict-7 ; %d  \n",idN2,idN3,conflict);
				}
			}
		}


		if(DEBUGANH) printf("Conflict link (%d,%d) = %d\n",id1,id2,conflict);
	return conflict;
}

//Compute the conflict graph for a link directional with a conflict at 3 hops.
int conflictGraphLink3(int emetteur, int recepteur, int frequency)
{
	   int i, j, idN1, idN2, idN3, conflict=0;

		    // si id1 et id2 ne sont pas de voisin
		    if(isNeighbor(emetteur,recepteur)==0)
		    	return -1;

		    //ne compte pas le lien sans frequency
		    if( VIDE==frequency)
		    	return -1;

		    /////////////////////////////////////
		    //  Traitement auprès du noeud id1 //
		    /////////////////////////////////////
			for(i=0;i<nodes[emetteur].nbN1;i++)
			{
				idN1=nodes[emetteur].N1[i].id;//index of the neighbor

				//direct neighbor
				if(linkFrequencyRoute(emetteur,idN1,frequency)&&(idN1!=recepteur)){
					conflict++;
//					if(DEBUGANH) printf("link (%d,%d) in conflict-1: %d\n",emetteur,idN1,conflict);
				}

				//2 1-neighbors together
				for(j=i+1;j<nodes[emetteur].nbN1;j++){
					if(linkFrequencyRoute(idN1,nodes[emetteur].N1[j].id,frequency)==1){
						conflict++;
//						if(DEBUGANH) printf("link (%d,%d) in conflict-2; %d\n",idN1,nodes[emetteur].N1[j].id,conflict);
					}
				}

				//neighbor with 2-neighbors
				for(j=0;j<nodes[emetteur].nbN2;j++){
					if(linkFrequencyRoute(idN1,nodes[emetteur].N2[j].id,frequency)==1){
						conflict++;
//						if(DEBUGANH) printf("link (%d,%d) in conflict-3; %d \n",idN1,nodes[emetteur].N2[j].id,conflict);
					}
				}

			}

			//2 2-neighbors together
			for(i=0;i<nodes[emetteur].nbN2;i++)
			{
				idN2 = nodes[emetteur].N2[i].id;//index of the neighbor
				for(j=i+1;j<nodes[emetteur].nbN2;j++)
				{
					if(linkFrequencyRoute(idN2,nodes[emetteur].N2[j].id,frequency)==1)
					{
						conflict++;
//						if(DEBUGANH) printf("link (%d,%d) in conflict-4; %d\n",idN2,nodes[emetteur].N2[j].id,conflict);
					}
				}
			}

			//neighbor with 3-neighbors of node id1
			for(i=0;i<nodes[emetteur].nbN2;i++)
			{
				idN2 = nodes[emetteur].N2[i].id;
				for(j = 0 ; j < nodes[idN2].nbN1;j++)
				{
					idN3 = nodes[idN2].N1[j].id;
					if( is3Neighbor(emetteur,idN3) && (linkFrequencyRoute(idN2,idN3,frequency)==1) )
					{
						conflict++;
//						if(DEBUGANH) printf("link (%d,%d) in conflict-5 ; %d\n",idN2,idN3,conflict);
					}
				}
			}


			   /////////////////////////////////////
			   //  Traitement auprès du noeud id2 //
			   /////////////////////////////////////

			//2 2-neighbors together
				for(i=0;i<nodes[recepteur].nbN2;i++)
				{
					idN2 = nodes[recepteur].N2[i].id;//index of the neighbor
					for(j=i+1;j<nodes[recepteur].nbN2;j++)
					{
						if(linkFrequencyRoute(idN2,nodes[recepteur].N2[j].id,frequency)==1)
						{
							conflict++;
//							if(DEBUGANH) printf("link (%d,%d) in conflict-6; %d\n",idN2,nodes[recepteur].N2[j].id,conflict);
						}
					}
				}

		      // 3-neighbors of node id2
				for(i = 0 ; i < nodes[recepteur].nbN2;i++)
				{
					idN2 = nodes[recepteur].N2[i].id;
					for(j = 0 ; j < nodes[idN2].nbN1;j++)
					{
						idN3 = nodes[idN2].N1[j].id;

						// idN3 est le voisinage 3-sauts de id2 et idN2 est l'emetteur ==> conflict
						// et idN3 n'est pas de voisinage 1,2,3 saut de id1
						if((linkFrequencyRouteDirectionnel(idN2,idN3,frequency)==1) && (is3Neighbor(recepteur,idN3)==1)
						   && (isNeighbor(emetteur,idN3)==0) && (is2Neighbor(emetteur,idN3)==0) && (is3Neighbor(emetteur,idN3)==0))
						{
							conflict ++;
//							if(DEBUGANH) printf("link (%d,%d) in conflict-7 ; %d \n",idN2,idN3,conflict);
						}
					}
				}


//		    if(DEBUGANH) printf("Conflict link (%d,%d) = %d\n",emetteur,recepteur,conflict);
			return conflict;
}

////////////////////////////////////////////////////////////
// 	Algorithme : l'assignation des fréquences en réseau   //
////////////////////////////////////////////////////////////

//Alloue la meme frequence vide partout (frequence -1) et sur la meme radio (-1) les autres radios ne sont pas alloues
void allocateEmptyFrequency()
{
	int id,radio,j;

	//On assigne toutes les radios de tous les noeuds sur la freq vide
	for(id=0;id<nbOfNodes;id++)
	{
		for(radio=0;radio<nbOfRadios;radio++)
			nodes[id].frequency[radio]=VIDE;

		//On fixe les radios/freq vers les voisins a (0,0)
		for(j=0;j<nodes[id].nbN1;j++)
		{
			nodes[id].N1[j].frequency=VIDE;
			nodes[id].N1[j].radio=VIDE;
		}
	}

}

// Nous calculons le conflict directionnel ou bidirectionnel ici
int conflictGraphGeneric(int vertex1, int vertex2)
{

	// récuperer index
	int idVetex2 = getIndexN1(nodes[vertex1],vertex2);
	int frequence = nodes[vertex1].N1[idVetex2].frequency;

	int IE; 	// IE = nombre de conflict + 1

	// Global variables : directionnels
	// If 1 there is conflict directional
	// If 0 there is conflict bidirectional
	if(directionnels == 0)
	{
		//Compute the conflict graph for a link bidirectional with a conflict at 3 hops.
		IE = conflictGraphLink2(vertex1,vertex2,frequence) + 1 ;
	}
	else if(directionnels == 1)
	{
		//Compute the conflict graph for a link directional with a conflict at 3 hops.
		IE = conflictGraphLink3(vertex1,vertex2,frequence) + 1;
	}

	return IE;
}

// Rechercher la plus petite capacité sur le chemin pathNumber
float calculMinCapaciteChemin(int pathNumber)
{
	int source = 0;
	int destination = nbOfNodes - 1;
	int next = nodes[source].routingTable[pathNumber].nextHop;

	//Si cette route ne peut pas arriver à la destination, on returne la valeur zéro
	if(nodes[source].routingTable[pathNumber].destination ==-1)
	{
		// sauvegarder la plus petite valeur  B(i)/IE(i) sur le chemin pathNumber
		nodes[source].routingTable[pathNumber].cost2 = 0.0;
		return 0.0;
	}


	// fonction getMetric : prendre le débit sur le lien (source,next)
	// fonction conflictGraphGeneric : calculer le conflict (IE) pour le lien (source,next)

	float min ;
	if(conflictGraphGeneric(source,next) > 0 )
	{
		min =  (1.0 * getMetric(source,next)) / (conflictGraphGeneric(source,next) * 1.0);
	}
	else // dans ce cas, ce lien a la fréquence vide (conflictGraphGeneric(source,next) est égale -1)
	{
		/*
		 *         vide     f1     f2
		 * 		S -------A------B-----D
		 *
		 * */

		min =  0.0;
	}

	//parcourir le chemin pathNumber
	do
	{
		source = next;
		next = nodes[source].routingTable[pathNumber].nextHop;
		int conflict = conflictGraphGeneric(source,next) ;

		if(conflict > 0 )
		{
			float capacite = (1.0 * getMetric(source,next)) / (conflictGraphGeneric(source,next) * 1.0);
			if(capacite < min || min == 0.0)
				min = capacite;
		}


	}while(next != destination);

	// sauvegarder la plus petite valeur  B(i)/IE(i) sur le chemin pathNumber
	nodes[source].routingTable[pathNumber].cost2 = min;
	return min;
}

// Calculer la capacité du réseau
float calculCapaciteReseau(int nbOfRoutes)
{
	int i;
	float capacite = 0.0;
	for (i=0 ; i < nbOfRoutes ; i++)
		capacite += calculMinCapaciteChemin(i);

	return capacite;
}

// compter le nombre de 'freq' qui avait utilisé sur le noeud vertex1
int countFrequency( vertex1, freq)
{

	if(freq==VIDE)
		return -1;

	int resul = 0 ;
	int i;
	for(i=0;i < nodes[vertex1].nbN1 ; i++)
		if(nodes[vertex1].N1[i].frequency == freq)
			resul ++;

	return resul;
}

// compter le nombre de radio qui avait utilisé sur le noeud vertex1
int countRadio ( int vertex1 )
{
	int resul = 0 ;
	int i;
	for(i=0;i < nbOfRadios ; i++)
		if(nodes[vertex1].frequency[i] != -1)
			resul ++;

	return resul;
}

// Changer la fréquence entre deux noeuds vertex1 et vertex2
// Returner -1, si il est impossible
int updateFreq(int vertex1,int vertex2, int frequence)
{

	// récuperer index
	int idVetex1 = getIndexN1(nodes[vertex2],vertex1);
	int idVetex2 = getIndexN1(nodes[vertex1],vertex2);

	// la fréquence commune entre vertex1 et vertex2
	int freq = nodes[vertex1].N1[idVetex2].frequency;

	// s'il y a déjà cette fréquence
	if(freq == frequence)
		return 1;


	// compter le nombre de 'freq' qui avait utilisé sur le noeud vertex1 et le noeud vertex2
	// Si fre est la fréquence vide, return -1
	int numOldFreqNode1 = countFrequency( vertex1, freq);
	int numOldFreqNode2 = countFrequency( vertex2, freq);

	// compter le nombre de 'frequence' qui avait utilisé sur le noeud vertex1 et le noeud vertex2
	// Si 'frequence' est la fréquence vide, return -1
	int numNewFreqNode1 = countFrequency( vertex1, frequence);
	int numNewFreqNode2 = countFrequency( vertex2, frequence);

	// compter le nombre de radio qui avait utilisé sur le noeud vertex1
	int numRadioNode1 = countRadio ( vertex1 );

	// compter le nombre de radio qui avait utilisé sur le noeud vertex2
	int	numRadioNode2 = countRadio ( vertex2 );

	int passNode1 = numNewFreqNode1 > 0 || numOldFreqNode1 == 1 || numRadioNode1 < nbOfRadios || frequence==VIDE;
	int passNode2 = numNewFreqNode2 > 0 || numOldFreqNode2 == 1 || numRadioNode2 < nbOfRadios || frequence==VIDE;

	int newRadioIndex = -1;

	// Si nous pouvons changer la fréquence
	if (passNode1 && passNode2)
	{

		// Mis à jour la nouvelle fréquence sur le noeud vertex1 et vertex2
		nodes[vertex1].N1[idVetex2].frequency=frequence;
		nodes[vertex2].N1[idVetex1].frequency=frequence;

		// Changement la radio sur le noeud vertex1
		if (numOldFreqNode1 != 1 && numNewFreqNode1 == 0)
		{
			int newRadioNode1 = freeRadio(vertex1); // Chercher la premiere radio disponible sur le noeud 1
			nodes[vertex1].N1[idVetex2].radio = newRadioNode1;
			nodes[vertex1].frequency[newRadioNode1]=frequence;
		}
		else
		{
			if (numNewFreqNode1 == 0)
			{
				// Rechercher newRadioIndex de 'freq' sur le noeud vertex1
				newRadioIndex = usedfreq( vertex1,freq );
			} else
			{
				// Rechercher newRadioIndex de 'frequence' sur le noeud vertex1
				newRadioIndex = usedfreq( vertex1,frequence );

				// Supprimer freq, si nous ne l'utilise plus
				if ( numOldFreqNode1 == 1 )
					nodes[vertex1].frequency[ usedfreq(vertex1,freq) ] = -1;
			}
			// nodes[vertex1].N1[idVetex2].radio <-- newRadioIndex
			nodes[vertex1].N1[idVetex2].radio = newRadioIndex;
			nodes[vertex1].frequency[nodes[vertex1].N1[idVetex2].radio]=frequence;
		}

		// Changement la radio sur le noeud vertex2
		if (numOldFreqNode2 != 1 && numNewFreqNode2 == 0)
		{
			int newRadioNode2 = freeRadio(vertex2); // Chercher la premiere radio disponible sur le noeud 2
			nodes[vertex2].N1[idVetex1].radio = newRadioNode2;
			nodes[vertex2].frequency[newRadioNode2]=frequence;
		}
		else
		{
			if (numNewFreqNode2 == 0)
			{
				// Rechercher newRadioIndex de 'freq' sur le noeud vertex2
				newRadioIndex = usedfreq( vertex2,freq );
			}
			else
			{
				// Rechercher newRadioIndex de 'frequence' sur le noeud vertex2
				newRadioIndex = usedfreq( vertex2,frequence );

				// Supprimer freq, si nous ne l'utilise plus
				if ( numOldFreqNode2 == 1 )
					nodes[vertex2].frequency[ usedfreq(vertex2,freq) ] = -1;
			}
			// nodes[vertex2].N1[idVetex1].radio <-- newRadioIndex
			nodes[vertex2].N1[idVetex1].radio = newRadioIndex;
			nodes[vertex2].frequency[nodes[vertex2].N1[idVetex1].radio]=frequence;
		}

		return 1;
	}

	return -1;
}


// Trouver la fréquence pour le lien (vertex1,vertex2) qui nous donne la plus grande capacité soit supérieur à la capacité du réseau en cours
float assignationLien(int vertex1, int vertex2,int nbOfRoutes)
{

	int i,nbOfFa,nbOfFs,nbOfFreq;
	float max = 0.0;

	// récuperer index de vertex2
	int idVetex2 = getIndexN1(nodes[vertex1],vertex2);
	int bestFreq = nodes[vertex1].N1[idVetex2].frequency;


	int Freq[maxFreq]; // la liste de fréquence à parcourir
	for (i=0 ; i < maxFreq ; i++)
		Freq[i] = -1;


	nbOfFa=nbOfFs=nbOfFreq = 0;
	for(i = 0 ; i < nbOfRadios ; i++)
	{
		if(nodes[vertex1].frequency[i] != -1)
			nbOfFs ++;

		if(nodes[vertex2].frequency[i] != -1)
			nbOfFa ++;
	}

//	int cas = 0;

	// Le noeud vertex1 et vertex2 ont encore des radios libres, la liste Freq contient toutes les fréquences
	if((nbOfFs < nbOfRadios) && (nbOfFa < nbOfRadios))
	{
//		cas = 1;
		nbOfFreq = maxFreq;
		for(i = 0 ; i < maxFreq ; i++)
			Freq[i] = i;
	}
	// le noeud vertex2 n'a plus de radio libre, la liste Freq contient toutes les fréquences de noeud vertex2
	else if ((nbOfFs < nbOfRadios) && (nbOfFa == nbOfRadios))
	{
//		cas = 2;
		for(i = 0 ; i < maxFreq ; i++)
		{
			if(usedfreq(vertex2,i) != -1)
			{
				Freq[nbOfFreq] = i;
				nbOfFreq ++;
			}
		}

	}
	// le noeud vertex1 et vertex2 n'ont plus de radio libre, la liste Freq contient toutes les fréquences commumes
	else if((nbOfFs == nbOfRadios) && (nbOfFa == nbOfRadios))
	{
//		cas = 3;
		for(i = 0 ; i < maxFreq ; i++)
		{
			if ((usedfreq(vertex1,i) != -1) && (usedfreq(vertex2,i) != -1))
			{
				Freq[nbOfFreq] = i;
				nbOfFreq ++;
			}
		}
	}
	// le noeud vertex1 n'a plus de radio libre, la liste Freq contient toutes les fréquences de noeud vertex1
	else if((nbOfFs == nbOfRadios) && (nbOfFa < nbOfRadios))
	{
//		cas = 4;
		for(i = 0 ; i < maxFreq ; i++)
		{
			if(usedfreq(vertex1,i) != -1)
			{
				Freq[nbOfFreq] = i;
				nbOfFreq ++;
			}
		}
	}

	// Parcourir la liste de fréquence
	for(i = 0 ; (i < nbOfFreq) && (Freq[i] != -1); i++)
	{
//		int test = Freq[i];
		// Changement la fréquence de lien (vertex1,vertex2) par la fréquence Freq[i]
		if(updateFreq(vertex1,vertex2,Freq[i]) == 1)
		{
			// Recalculer la capacité du réseau
			float capacite = calculCapaciteReseau(nbOfRoutes);
			if(capacite > max)
			{
				max = capacite ;
				bestFreq = Freq[i];
			}
		}
	}

	updateFreq(vertex1,vertex2,bestFreq);
	return max;
}

// Vérifier que le lien (vertex1,vertex2) exist déjà sur la route pathNumber.
// Si oui, retourner 1.
// Si non, retourner -1
int existLienSurRoute(int vertex1, int vertex2,int pathNumber)
{
	int source = 0;
	int destination = nbOfNodes - 1;
	int next = nodes[source].routingTable[pathNumber].nextHop;

	do
	{
		if ( (source==vertex1 && next==vertex2) || (source==vertex2 && next==vertex1) )
			return 1;

		source = next;
		next = nodes[source].routingTable[pathNumber].nextHop;
	}while (source != destination);

	return -1;
}

// Vérifier que le lien (vertex1,vertex2) appartient juste la route 'pathNumber'
// Si oui, retourner 1.
// Si non, retourner -1
int existJusteLien(int vertex1, int vertex2,int pathNumber, int nbOfRoutes)
{
	int i;

	// Si le lien (vertex1,vertex2) n'appartient pas la route 'pathNumber'
	if(existLienSurRoute(vertex1,vertex2,pathNumber) == -1)
		return -1;

	// Si le lien (vertex1,vertex2) appartient des routes qui sont différentes à la route 'pathNumber'
	for(i = 0 ; i < nbOfRoutes ; i++)
		if( i != pathNumber && existLienSurRoute(vertex1,vertex2,i) == 1)
			return -1;

	return 1;
}

// on remet la fréquence vide aux liens sur le chemin pathNumber
void initialisationChemin(int pathNumber,int nbOfRoutes)
{
	int source = 0;
	int destination = nbOfNodes - 1;
	int next = nodes[source].routingTable[pathNumber].nextHop;


	fprintf(stderr,"La route %d est supprimee car elle dimimue la capacite\n",pathNumber);
	do
	{
		// Si ce lien appartient juste la route 'pathNumber', nous y mettons la fréquence vide
		if(existJusteLien(source,next,pathNumber,nbOfRoutes) == 1)
		{
			//Assignation la fréquence vide (-1)
			updateFreq(source,next, VIDE);
		}
		//On met la route a -1 ici pour pas qu'elle ne soit pas utilise dans le routage statique
		nodes[source].routingTable[pathNumber].destination=-1;

		source = next;
		next = nodes[source].routingTable[pathNumber].nextHop;

	}while (source != destination);
}

void affichageReseau()
{
	fprintf(stderr,"\n");
	int id,id2;
	for(id=0;id<nbOfNodes;id++)
    	for(id2=0;id2<nodes[id].nbN1;id2++)
    		if(nodes[id].N1[id2].frequency > -1)
    		{
    			fprintf(stderr,"-Assignation link (%d, %d) radio=%d freq=%d Debit:%d IE=%d\n",
						  id,nodes[id].N1[id2].id,nodes[id].N1[id2].radio,
						  nodes[id].N1[id2].frequency,getMetric(id,nodes[id].N1[id2].id),
						  conflictGraphGeneric(id,nodes[id].N1[id2].id));

    		}

	fprintf(stderr,"\n");
}

//Allocate the frequency to the nodes
//nbOfRoutes is number routing between node source and destination
void allocateFrequencyAnh(int nbOfRoutes)
{
	int i, source, destination,next;

	// Initialisation du réseau : aucune fréquence
	allocateEmptyFrequency();


	float maxCapacite = 0.0; // la capacité du réseau en cours
	float maxLocal = 1.0; // la capacité locale

	for(i = 0 ; i < nbOfRoutes; i++) // parcourir la liste de route
	{
		source = 0;
		destination = nbOfNodes - 1;
		next = nodes[source].routingTable[i].nextHop;

		while ((maxLocal >= maxCapacite) && (source != destination))
		{
			// Trouver la fréquence pour le lien (vertex1,vertex2)
			// qui nous donne la plus grande capacité soit supérieure à maxCapacite
			maxLocal = assignationLien(source,next,nbOfRoutes);

	//		affichageReseau();

			source = next;
			next = nodes[source].routingTable[i].nextHop;
		}

		// affichageReseau();

		if(maxLocal >= maxCapacite) // Si la capacité du réseau est augmentée, on met à jour sa valeur
		{
			maxCapacite = maxLocal;
			maxLocal ++;
		}
		else // on remet la fréquence vide aux liens sur ce chemin
		{
			initialisationChemin(i,nbOfRoutes);
		}

	}

	 maxCapacite=calculCapaciteReseau(nbOfRoutes);


	// sauvegarder la valeur B(i)/IE(i) dans cost2; sert a fixer le debit de la source
	for(i = 0 ; i < nbOfRoutes ; i++) // parcourir la liste de route
		if(nodes[0].routingTable[i].destination>=0)
			nodes[0].routingTable[i].cost2 = calculMinCapaciteChemin(i);

	fprintf(stderr,"maxCapacite(Anh)=%f\n",maxCapacite);
	affichageReseau();

}//End of the function allocateFrequencyAnh()





